package Algorithm.dynamicProgramming.knapsackDp;

/**
 * 322. 零钱兑换 https://leetcode.cn/problems/coin-change
 * 题目简述：一个整数数组表示不同面额的硬币，每种硬币有无限个，求用硬币凑成一个总金额所需的最少硬币个数，凑不成则返回-1
 */
public class CoinChange {

    /**
     * 思路：完全背包-装满最小价值问题。金额对应重量，每个物品的价值都是1，求装满背包的最小价值
     * 1. 定义dp：dp[i][j]为刚好装满容量为j的背包时从前i种硬币中选能获得的最小价值，若无法装满则为-1
     * 2. 状态转移公式：分以下两种情况，求最小价值，故dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i-1]] + 1)，若其中有-1则直接取另一个值
     *          （1）当不选第i种硬币时，dp[i][j] = dp[i-1][j]
     *          (2) 当选k个第i种硬币时，dp[i][j] = dp[i][j - coins[i-1]] + 1
     * 3. 初始化：当背包重量为0时，可装0个硬币，故dp[i][0] = 0；当没有硬币但是背包重量大于0时，肯定无法装满，故dp[0][j] = -1
     */
    public int coinChange(int[] coins, int amount) {
        int[][] dp = new int[coins.length+1][amount+1];
        for (int j  = 1;j <= amount;j++)
            dp[0][j] = -1;
        for (int i = 1;i <= coins.length;i++) {
            for (int j = 1;j <= amount;j++) {
                //若第i件物品重量直接超过了j，或者若选择第i种物品就无法装满，则dp[i][j] = dp[i-1][j];
                if (j < coins[i-1] || dp[i][j - coins[i-1]] == -1) dp[i][j] = dp[i-1][j];
                //否则若从前i-1件物品中选择无法装满，则dp[i][j] = dp[i][j - coins[i-1]] + 1;
                else if (dp[i-1][j] == -1) dp[i][j] = dp[i][j - coins[i-1]] + 1;
                //否则若两种情况都可以，则取最小值
                else dp[i][j] = Math.min(dp[i-1][j], dp[i][j - coins[i-1]] + 1);
            }
        }
        return dp[coins.length][amount];
    }

    public int coinChange2(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for (int j  = 1;j <= amount;j++)
            dp[j] = -1;
        for (int i = 1;i <= coins.length;i++) {
            for (int j = 1;j <= amount;j++) {
                //若第i件物品重量直接超过了j，或者若选择第i种物品就无法装满，则dp[i][j] = dp[i-1][j];
                if (j < coins[i-1] || dp[j - coins[i-1]] == -1) dp[j] = dp[j];
                //否则若从前i-1件物品中选择无法装满，则dp[i][j] = dp[i][j - coins[i-1]] + 1;
                else if (dp[j] == -1) dp[j] = dp[j - coins[i-1]] + 1;
                //否则若两种情况都可以，则取最小值
                else dp[j] = Math.min(dp[j], dp[j - coins[i-1]] + 1);
            }
        }
        return dp[amount];
    }
}
